class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0,len = nums.size(),p = 0;
        for(auto& x:nums) sum += x;
        if(sum%2) return false;
        sum /= 2;
        vector<bool> k(sum,false);
        k[0] = true;
        for(int j = 0,pre = p; j < len; ++j){
            for(int i = p; i >= 0; --i){//p剪枝
                if(k[i]){
                    if(i+nums[j] == sum) return true;
                    else if(i+nums[j] < sum) k[i+nums[j]] = true;
                    pre = max(pre,min(i+nums[j],sum-1));
                }
            }
            p = pre;
        }
        return false;
    }
};

